Finite state models (FSMs) have been extensively applied to many aspects of language processing including speech recognition, phonology, morphology, chunking and parsing. FSMs are attractive mechanisms for language processing because they are efficiently learnable from data and generally effective for decoding. Also, FSMs are associated with a calculus for composing a model, which allows for straightforward integration of constraints from various levels of language processing.
A conventional machine translation process includes two phases: (a) lexical choice phase where appropriate target language lexical items are chosen for each source language lexical item; and (b) reordering phase where the chosen target language lexical items are reordered to produce a meaningful target language string. With respect to the lexical choice phase, the conventional methods for constructing a bilingual lexicon use a string-based alignment. However, these conventional approaches incur the expense of creating a permutation lattice for recording and are, thus, less attractive.